The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
In communication systems, channel noise may cause transmission errors between a source and a receiver. Error correction coding (ECC) may detect and correct channel transmission errors. Low-density parity-check (LDPC) codes are examples of ECC block codes that may be used to detect and correct channel transmission errors.
FIG. 1 shows a functional block diagram of a communication system 10. The communication system 10 may include an encoder 12, a modulator 14, a channel 16, a demodulator 18, and an iterative decoder 20. The iterative decoder 20 may include a channel detector 22 and a decoder 24. For example, the encoder 12 and the decoder 24 may use an LDPC code.
Using the LDPC code, the encoder 12 encodes a stream of datawords (u) from a source. A dataword may refer to a group of binary data bits that is suitable for input to the encoder 12. The encoder 12 outputs a stream of codewords (c), which may be in the form of binary data. A codeword may refer to a group of bits generated by the encoder 12 based on an input dataword.
LDPC codes are block codes. An LDPC code may be represented by an (M×N) parity-check matrix (H) that includes M rows and N columns. M may represent a number of constraints, such as parity-check equations. N may represent a number of bits. Entries of the parity-check matrix may be ones or zeros.
The modulator 14 modulates the frequency, amplitude, and/or phase of the stream of codewords to generate a transmit signal (w) that includes a modulated communication signal or a modulated storage signal (hereinafter a modulated signal). For example, the channel 16 may include a storage medium, such as a magnetic storage medium, an optical storage medium, or a memory integrated circuit. The channel 16 may also include a communication channel (e.g., a wireless or a wireline communication channel). The channel 16 provides a receive signal (w′), which may represent the transmit signal corrupted by noise (n) or other interference.
The demodulator 18 demodulates the receive signal and provides an initial estimate signal (r′) of the stream of codewords. The channel detector 22 of the iterative decoder 20 receives the initial estimate signal, which may be based on hard information in blocks of data. The initial estimate signal may include corrupted bits. Hard information represents hard decisions on whether data bits are ones or zeros. For example, a hard decision for a bit may be either a one or a zero.
The channel detector 22 may generate soft information via a soft decision that is based on the initial estimate signal and data from the channel 16. Soft information represents soft decisions on whether data bits are ones or zeros. For example, a soft decision for a bit may be a real number that represents a probability or a likelihood of belief (e.g., a log-likelihood ratio or LLR) that the bit is a one or a zero.
For example, the channel detector 22 may generate the soft information based on the Viterbi algorithm. The channel detector 22 may also generate the soft information based on channel factors such as a type of modulation used by the modulator 14 and channel parameters such as additive white Gaussian noise (AWGN).
The decoder 24 receives the soft information and may attempt to satisfy M parity-check equations of the parity-check matrix using the soft information. However, if one or more of the parity-check constraints are not satisfied, the decoder 24 may generate feedback information. For example, a message-passing algorithm such as a sum-product algorithm may be used to generate the feedback information. In such an example, feedback messages from check nodes may be summed to generate the feedback information for a bit.
The channel detector 22 receives the feedback information and may update the soft information from the channel based on the feedback information. For example, the channel detector 22 may sum the soft information and the feedback information to generate updated soft information. The decoder 24 receives the updated soft information, and the process repeats.
For example, the iterative decoder 20 may repeat the process for numerous iterations to decode an entire block of data. The iterative decoder 20 may continue until a valid codeword is found that satisfies all M parity-check equations. The iterative decoder 20 may also continue until an allotted time has elapsed or when a certain number of iterations have occurred.
The iterative decoder 20 generates an estimate signal (r) based on the soft information and the iterative decoding process. The estimate signal represents an estimate of the original transmitted stream of datawords. For example, the estimate signal may include the most likely datawords. The estimate signal may also include the original stream of datawords if no error exists.
Referring now to FIG. 2A, the decoder 24 may include a plurality of nodes 30. The nodes 30 illustrate the iterative message-passing process between variable and check nodes that is used by a typical decoder 24. For example, the nodes 30 represents the following parity-check matrix H:
  H  =            [                                    1                                1                                1                                0                                0                                0                                                1                                0                                0                                1                                1                                0                                                0                                1                                1                                0                                0                                1                                                0                                0                                0                                1                                1                                1                              ]        .  
The nodes 30 may include check nodes c0 (34-0), c1 (34-1), c2 (34-2), and c3 (34-3) (collectively referred to as check nodes 34). The nodes 30 may also include variable nodes v0 (36-0), v1 (36-1), v2 (36-2), v3 (36-3), v4 (36-4), and v5 (36-5) (collectively referred to as variable nodes 36).
FIG. 2B shows the relationship between the check nodes 34, the variable nodes 36, and the parity-check matrix H. The variable nodes 36 correspond to the N columns of the parity-check matrix H. The check nodes 34 correspond to the M rows of the parity-check matrix H.
The interacting nodes 30 may be referred to as a bipartite graph (called a Tanner graph) because no nodes of the same type (i.e., variable nodes and check nodes) are connected to each other. Communication lines (called edges) connect check nodes 34 to variable nodes 36. For example, one of the check nodes 34 is connected to one of the variable nodes 36 if the corresponding entry in the parity-check matrix is a one. For example, check node c0 (34-0) is connected to variable node v0(36-0) because H0,0=1.
Information received from the channel 16 is communicated to the variable nodes 36 via the channel detector 22. The variable nodes 36 may pass the information up to the check nodes 34. For example, variable node v0 (36-0) may pass a message (i.e., channel information) to check nodes c0 (34-0) and c1 (34-1) because the nodes are connected.
The check nodes 34 may compute messages based on the information received from the variable nodes 36. For example, one of the check nodes 34 may compute a message by summing all messages received from variable nodes 36. The check nodes 34 may then pass the messages back to respective variable nodes 36.
For example, check node c0 (34-0) may compute a message by summing messages received from variable nodes v0 (36-0), v1 (36-1), and v2 (36-2) because the nodes are connected. Check node c0 (34-0) may also send the message back to variable nodes v0 (36-0), v1 (36-1), and v2 (36-2) because the nodes are connected.
The variable nodes 36 may then compute messages based on the messages received from the check nodes 34. For example, one of the variable nodes 36 may compute a message by summing all messages received from check nodes 34. For example, variable node v0 (36-0) may compute a feedback signal by summing messages received from check nodes c0 (34-0) and c1 (34-1) because the nodes are connected.
The check nodes 34 may send the feedback signals back to the channel detector 22. The channel detector 22 may generate updated soft information based on the feedback signals and the soft information. The decoder 24 then receives the updated soft information.
The iterative message-passing process may be repeated until a predetermined condition is satisfied. After the predetermined condition is satisfied, the iterative decoder 20 may generate and output an estimate signal r. For example, the iterative message-passing process may continue until a predetermined number of iterations have occurred or until all parity-check equations are satisfied. For example, the parity-check equations corresponding to the parity-check matrix H are:c0=v0+v1+v2 c1=v0+v3+v4 c2=v1+v2+v5 c3=v3+v4+v5.
FIG. 3A shows an example of a variable node computation. A variable node 38 receives an initial bit estimate (y), which may be an LLR, from the channel detector 22. The variable node 38 may also receive return messages x0, x1, and x2 from different check nodes. The variable node 38 may generate return messages based on the received return messages and the initial bit estimate. For example, as shown in FIG. 3B, the variable node 38 may generate return messages for each check node by summing all of the other received messages.